package sort.quicksort.util;

import org.junit.Test;
import sort.util.SortUtil;

import java.util.Random;

public class QuickSort {

    final static Random random = new Random(System.currentTimeMillis());


    public void sort(Comparable[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
//        int partition = partition(nums, start, end);
        int partition = partition_2(nums, start, end);

        sort(nums, start, partition-1);
        sort(nums, partition + 1, end);
    }

    //单路快排版本
    public int partition(Comparable[] nums, int start, int end) {
        int randomIndex = start + random.nextInt(end - start + 1); //产生 [start,end]的随机索引
        SortUtil.swap(nums, randomIndex, start);

        Comparable pivot = nums[start];
        int i = start;
        int j ;

        for (j = start+1; j <= end; j++) {
            if (SortUtil.greater(pivot, nums[j])) {
                i++;
                SortUtil.swap(nums, i, j);
            }
        }
        SortUtil.swap(nums, start, i );
        return i ;
    }

    //双路快排版本
    public int partition_2(Comparable[] nums, int start, int end) {
        int randIndex = start + random.nextInt(end - start + 1);
        SortUtil.swap(nums, start, randIndex);
        Comparable pivot = nums[start];
        int left = start+1;
        int right = end;


        while (true) {
            while (left <= right && SortUtil.greater(pivot, nums[left])) {
                left++;
            }

            while (left <= right && SortUtil.greater(nums[right], pivot)) {
                right--;
            }

            if (left >= right) {
                break;
            }
            SortUtil.swap(nums, left, right);
            left++;
            right--;
        }

        SortUtil.swap(nums, start, right);
        return right;
    }

    //三路快排版本
    public void sort_3(Comparable[] nums, int start, int end) {
        int randIndex = start + random.nextInt(end - start + 1);
        SortUtil.swap(nums, start, randIndex);
        Comparable pivot = nums[start];

        int left = start+1;
        int right = end;
        int i = start + 1;
//
        while (i <= right) {
            if (nums[i].compareTo(pivot) < 0) {
                SortUtil.swap(nums, i, left);
                // i!=left,说明从 left所指向的元素值此时为pivot，所以当i处和left处进行交换之后，i处的值
                //就是pivot，不需要再进行检查了，所以直接i++
                i++;
                left++;
            } else if (nums[i].compareTo(pivot) == 0) {
                i++;
            }else{
                SortUtil.swap(nums, i, right);
                right--;
            }
        }
    }

    @Test
    public void test() {
        Integer[] a = {6, 1, 2, 7, 9, 3, 4, 5, 8};
//        int[] a = {1,2,3,4,4,4,5,6,7};
        sort(a, 0, a.length - 1);
        SortUtil.display(a);
    }
}
